package web

import (
	"fmt"
	"regexp"
	"strings"
)

// 每个 http 请求方法都有一个自己的 router
type router struct {
	// 这里 map 中的 key 只能是 http 方法字符串
	trees map[string]*node
}

func newRouter() router {
	return router{
		trees: map[string]*node{},
	}
}

func (r *router) addRoute(method, path string, handler HandlerFunc, mdls ...Middleware) {
	// 路径合法检查
	if path == "" {
		panic("web: 路由是空字符串")
	}
	if path[0] != '/' {
		panic("web: 路由必须以 / 开头")
	}
	if path != "/" && path[len(path)-1] == '/' {
		panic("web: 路由不能以 / 结尾")
	}

	// 找到 http 方法对应的子树
	root, ok := r.trees[method]
	if !ok {
		root = &node{path: "/"}
		r.trees[method] = root
	}
	if path == "/" {
		if root.handler != nil {
			panic("web: 路由冲突[/]")
		}
		root.handler = handler
		root.route = path
		root.mdls = append(root.mdls, mdls...)
		return
	}

	// 把路径用 "/" 分割后，递归构建树上的子节点
	segs := strings.Split(path[1:], "/")
	for _, s := range segs {
		if s == "" {
			panic(fmt.Sprintf("web: 非法路由。不允许使用 //a/b， /a//b 形式的路由：[%s]", path))
		}

		// 用 s 去查找节点，找到匹配的直接返回，否则新建一个
		root = root.childOrCreate(s)
	}

	if root.handler != nil {
		panic(fmt.Sprintf("web: 路由冲突[%s]", path))
	}

	root.handler = handler
	root.route = path
	root.mdls = append(root.mdls, mdls...)
}

func (r *router) findRoute(method, path string) (*matchInfo, bool) {
	// 找到 http method 对应的树
	root, ok := r.trees[method]
	if !ok {
		return nil, false
	}

	if path == "/" {
		return &matchInfo{n: root, mdls: root.mdls}, true
	}

	// 根据斜杠拆分路径，递归处理
	segs := strings.Split(strings.Trim(path, "/"), "/")
	mi := &matchInfo{}
	cur := root
	for _, s := range segs {
		var child *node
		// 在子节点查找匹配，子节点如果匹配不上，再回溯到当前节点，如果当前节点是通配节点，就也算匹配上了
		child, ok = cur.childOf(s)
		if !ok {
			if cur.typ == nodeTypeAny {
				mi.n = cur
				return mi, true
			}
			return nil, false
		}

		// 记得把路径参数加上
		if child.paramName != "" {
			mi.addValue(child.paramName, s)
		}
		cur = child
	}
	mi.n = cur
	mi.mdls = r.findMdls(root, segs)

	return mi, true
}

// 按层遍历查找匹配的中间件
func (r *router) findMdls(root *node, segs []string) []Middleware {
	// 收集找到的所有中间件
	mdls := root.mdls

	// 下一层需要继续查找的节点集合
	var next_nodes []*node
	// 当前层要查找的节点
	cur_nodes := []*node{root}
	for _, s := range segs {
		// 根据同层中间的执行优先级，应该按如下顺序查找
		// cur.startChild
		// cur.regChild
		// cur.paramChild
		// cur.children

		// 遍历当前层
		for _, cur := range cur_nodes {
			// 查找通配符节点
			if cur.starChild != nil {
				if cur.starChild.mdls != nil {
					mdls = append(mdls, cur.starChild.mdls...)
				}
				next_nodes = append(next_nodes, cur.starChild)
			}

			// 查找正则节点
			if cur.regChild != nil {
				if cur.regChild.regExpr.Match([]byte(s)) {
					if cur.regChild.mdls != nil {
						mdls = append(mdls, cur.regChild.mdls...)
					}
					next_nodes = append(next_nodes, cur.regChild)
				}
			}

			// 查找路径参数节点
			if cur.paramChild != nil {
				if cur.paramChild.mdls != nil {
					mdls = append(mdls, cur.paramChild.mdls...)
				}
				next_nodes = append(next_nodes, cur.paramChild)
			}

			// 查找静态节点
			if cur.children != nil {
				n, ok := cur.children[s]
				if ok {
					if n.mdls != nil {
						mdls = append(mdls, n.mdls...)
					}
					next_nodes = append(next_nodes, n)
				}
			}
		}

		// 进入下一层
		if next_nodes != nil {
			cur_nodes = next_nodes
			next_nodes = nil
		}
	}

	return mdls
}

type nodeType int

const (
	nodeTypeStatic = iota
	nodeTypeReg
	nodeTypeParam
	nodeTypeAny
)

type node struct {
	typ nodeType

	// 当前节点上的路径字符串，创建节点的时候赋值
	path string
	// 到达节点的完整路由路径，在添加路由的最后赋值
	route string

	// 静态匹配，可以有多个子节点，其它都只能有一个子节点
	children map[string]*node
	// 通配符匹配
	starChild *node
	// 路径参数匹配
	paramChild *node
	paramName  string
	// 正则匹配
	regChild *node
	regExpr  *regexp.Regexp

	// 路由命中后执行
	handler HandlerFunc
	mdls    []Middleware
}

func (n *node) childOf(path string) (*node, bool) {
	// 静态匹配不存在或者匹配不上，才去找其它匹配方式
	if n.children == nil {
		return n.childOfNonStatic(path)
	}
	res, ok := n.children[path]
	if !ok {
		return n.childOfNonStatic(path)
	}
	return res, ok
}

func (n *node) childOfNonStatic(path string) (*node, bool) {
	// 先看看正则匹配
	if n.regChild != nil {
		if n.regChild.regExpr.Match([]byte(path)) {
			return n.regChild, true
		}
	}
	// 再看路径参数
	if n.paramChild != nil {
		return n.paramChild, true
	}

	return n.starChild, n.starChild != nil
}

// 同一个节点，多种匹配规则之间是互斥的，要注意检查
func (n *node) childOrCreate(path string) *node {
	// 通配符
	if path == "*" {
		if n.paramChild != nil {
			panic(fmt.Sprintf("web: 非法路由。已有路径参数路由，不允许同时注册通配符路由 [%s]", path))
		}
		if n.regChild != nil {
			panic(fmt.Sprintf("web: 非法路由。已有正则路由，不允许同时注册通配符路由 [%s]", path))
		}

		if n.starChild == nil {
			n.starChild = &node{path: path, typ: nodeTypeAny}
		}
		return n.starChild
	}

	// 路径参数或正则
	if path[0] == ':' {
		paramName, expr, isReg := n.parseParam(path)
		if isReg {
			return n.childOrCreateReg(path, expr, paramName)
		}
		return n.childOrCreateParam(path, paramName)
	}

	// 静态匹配
	if n.children == nil {
		n.children = map[string]*node{}
	}
	child, ok := n.children[path]
	if !ok {
		child = &node{path: path, typ: nodeTypeStatic}
		n.children[path] = child
	}
	return child
}

func (n *node) childOrCreateParam(path, paramName string) *node {
	if n.regChild != nil {
		panic(fmt.Sprintf("web: 非法路由，已有正则路由，不允许同时注册参数路由 [%s]", path))
	}
	if n.starChild != nil {
		panic(fmt.Sprintf("web: 非法路由，已有通配符路由，不允许同时注册参数路由 [%s]", path))
	}

	// 当前节点如果已有参数子节点，则要额外检查新来的和已有的是否一样
	if n.paramChild != nil {
		if n.paramChild.paramName != paramName {
			panic(fmt.Sprintf("web: 参数路由冲突，已有 [%s]，新注册 [%s]", n.paramChild.path, path))
		}
		return n.paramChild
	}

	n.paramChild = &node{path: path, paramName: paramName, typ: nodeTypeParam}

	return n.paramChild
}

func (n *node) childOrCreateReg(path, expr, paramName string) *node {
	if n.starChild != nil {
		panic(fmt.Sprintf("web: 非法路由，已有通配符路由，不允许同时注册正则路由 [%s]", path))
	}
	if n.paramChild != nil {
		panic(fmt.Sprintf("web: 非法路由，已有参数路由，不允许同时注册正则路由 [%s]", path))
	}

	regExpr, err := regexp.Compile(expr)
	if err != nil {
		panic(fmt.Errorf("web: 正则表达式错误 [%w]", err))
	}

	// 当前节点如果已有正则子节点，则要额外检查新来的和已有的是否一样
	if n.regChild != nil {
		if n.regChild.paramName != paramName || n.regChild.regExpr != regExpr {
			panic(fmt.Sprintf("web: 正则路由冲突，已有 [%s]，新注册 [%s]", n.paramChild.path, path))
		}
		return n.regChild
	}

	n.regChild = &node{path: path, paramName: paramName, regExpr: regExpr, typ: nodeTypeReg}
	return n.regChild
}

// 第一个返回值是参数名
// 第二个返回值是正则字符串
// 第三个返回值标识是否为正则匹配
func (n *node) parseParam(path string) (string, string, bool) {
	// 去掉开头的冒号
	path = path[1:]
	segs := strings.SplitN(path, "(", 2)
	if len(segs) == 2 {
		expr := segs[1]
		if strings.HasSuffix(expr, ")") {
			return segs[0], expr[:len(expr)-1], true
		}
	}
	return path, "", false
}

type matchInfo struct {
	n          *node
	pathParams map[string]string
	mdls       []Middleware
}

func (m *matchInfo) addValue(key, value string) {
	if m.pathParams == nil {
		m.pathParams = map[string]string{}
	}
	m.pathParams[key] = value
}
